package com.example.nirvana.dataStructure.algorithm;

/**
 * 优先级队列（最大堆）
 */
public class MaxPriorityQueue<Key extends Comparable<Key>> {
    // 存储元素的数组
    private Key[] pq;
    // 当前Priority Queue中的元素个数
    private int N = 0;

    public MaxPriorityQueue(int cap) {
        // 索引0不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    /**
     * 返回当前队列中最大元素
     * @return
     */
    public Key max() {
        return pq[1];
    }

    /**
     * 插入元素e
     *
     * @param e
     */
    public void insert(Key e) {
        N++;
        // 先把新元素加到最后
        pq[N] = e;
        // 然后让它上浮到正确的位置
        swim(N);
    }

    /**
     * 删除并返回当前队列中最大元素
     *
     * @return
     */
    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];
        // 把最大元素换到最后
        exch(1, N);
        pq[N] = null;
        N--;
        // 让pq[1]下沉到正确的位置
        sink(1);
        return max;
    }

    /**
     * 上浮第k个元素，已维护最大堆性质
     *
     * @param k
     */
    private void swim(int k) {
        // 如果浮到堆顶，就不能再上浮了
        while(k > 1 && less(parent(k), k)) {
            // 如果第k个元素比上层大
            // 将k换上去
            exch(parent(k), k);
            k = parent(k);
        }
    }

    /**
     * 下沉第k个元素，已维护最大堆性质
     *
     * @param k
     */
    private void sink(int k) {
        //如果沉到堆底，就沉不下去了
        while(left(k) <= N) {
            //先假设左边节点较大
            int older = left(k);
            //如果右边节点存在，比一下大小
            if (right(k) <= N && less(older, right(k))) {
                older = right(k);
            }
            //结点k比俩孩子都大，就不必下沉了
            if (less(older, k)) {
                break;
            }
            //否则，不符合最大堆的结构，下沉k结点
            exch(k, older);
            k = older;
        }
    }

    /**
     * 交换数组的两个元素
     *
     * @param i
     * @param j
     */
    private void exch(int i, int j) {
        Key temp = pq[j];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /**
     * 比较两个元素谁更小
     *
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    /**
     * 返回元素k的父节点下标
     *
     * @param k
     * @return
     */
    private int parent(int k) {
        return k/2;
    }

    /**
     * 返回元素k的左子节点下标
     *
     * @param k
     * @return
     */
    private int left(int k) {
        return k*2;
    }

    /**
     * 返回元素k的右子节点下标
     *
     * @param k
     * @return
     */
    private int right(int k) {
        return k*2 + 1;
    }
}
